"""
67. 二进制求和
https://leetcode.cn/problems/add-binary/
"""


class Solution:
    def method1(self, a: str, b: str) -> str:
        """
        思路1：
            转化为10进制，求和后再转化为2进制。
            进制转化的函数，可以用自带的，也可以自己写
            这里先用自带的，再自己写下机制转化
        """
        a10 = int(a, 2)
        b10 = int(b, 2)
        res = bin(a10+b10)[2:]
        return res

    def ten2bin(self, num: int) -> str:
        if num <= 1:
            return str(num)

        res = []
        while num:
            num, rem = divmod(num, 2)
            res.append(str(rem))
        return "".join(reversed(res))

    def bin2ten(self, binstr: str) -> int:
        if len(binstr) == 1:
            return int(binstr)

        res = 0
        for i, v in enumerate(binstr[::-1]):
            res += int(v)*(2**i)
        
        return res

    def method1_2(self, a: str, b: str) -> str:
        """
        思路1：
            转化为10进制，求和后再转化为2进制。
            进制转化的函数，可以用自带的，也可以自己写
            这里先用自带的，再自己写下机制转化
        """
        a10 = self.bin2ten(a)
        b10 = self.bin2ten(b)
        res = self.ten2bin(a10+b10)
        return res

    def method2(self, a: str, b: str) -> str:
        """
        思路2：
            直接二进制相加，满2进1
        """
        if len(a) > len(b):
            a, b = b, a  # 让a是小串
        # 将小串的高位补0和长串对齐，方便运算
        size = len(b)
        a = a.rjust(size, '0')

        # 反转下二进制串
        reversed_a = a[::-1]
        reversed_b = b[::-1]

        res = []
        jinwei = 0
        for i in range(len(b)):
            v = (int(reversed_a[i]) + int(reversed_b[i]) + jinwei)%2  # 当前位置的值
            jinwei = (int(reversed_a[i]) + int(reversed_b[i]) + jinwei)//2  # 需要进位的值
            res.append(str(v))
        
        # 最后处理可能最高位要进位的问题
        if jinwei !=0:
            res.append(str(jinwei))
        
        # 注意反转列表
        return "".join(res[::-1])
        


    def addBinary(self, a: str, b: str) -> str:

        # 思路1：使用自带的进制转化
        # return self.method1(a, b)

        # 思路2：使用自带的进制转化
        return self.method2(a, b)


def test():
    obj = Solution()
    # res = obj.bin2ten('110')
    # print(res)
    # res = obj.ten2bin(6)
    # print(res)
    res = obj.addBinary('11', '1')
    print(res)


if __name__ == "__main__":
    test()
